home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DJGPP / BNU22SR1.ZIP / src / binutils.2 / gprof / arcs.c next >
C/C++ Source or Header  |  1993-05-30  |  16KB  |  567 lines
  1. /*
  2.  * Copyright (c) 1983 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms are permitted
  6.  * provided that: (1) source distributions retain this entire copyright
  7.  * notice and comment, and (2) distributions including binaries display
  8.  * the following acknowledgement:  ``This product includes software
  9.  * developed by the University of California, Berkeley and its contributors''
  10.  * in the documentation or other materials provided with the distribution
  11.  * and in all advertising materials mentioning features or use of this
  12.  * software. Neither the name of the University nor the names of its
  13.  * contributors may be used to endorse or promote products derived
  14.  * from this software without specific prior written permission.
  15.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  16.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  17.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18.  */
  19.  
  20. #ifndef lint
  21. static char sccsid[] = "@(#)arcs.c    5.6 (Berkeley) 6/1/90";
  22. #endif /* not lint */
  23.  
  24. #include "gprof.h"
  25.  
  26.     /*
  27.      *    add (or just increment) an arc
  28.      */
  29. addarc( parentp , childp , count )
  30.     nltype    *parentp;
  31.     nltype    *childp;
  32.     long    count;
  33. {
  34.     arctype        *arcp;
  35.  
  36. #   ifdef DEBUG
  37.     if ( debug & TALLYDEBUG ) {
  38.         printf( "[addarc] %d arcs from %s to %s\n" ,
  39.             count , parentp -> name , childp -> name );
  40.     }
  41. #   endif DEBUG
  42.     arcp = arclookup( parentp , childp );
  43.     if ( arcp != 0 ) {
  44.         /*
  45.          *    a hit:  just increment the count.
  46.          */
  47. #    ifdef DEBUG
  48.         if ( debug & TALLYDEBUG ) {
  49.         printf( "[tally] hit %d += %d\n" ,
  50.             arcp -> arc_count , count );
  51.         }
  52. #    endif DEBUG
  53.     arcp -> arc_count += count;
  54.     return;
  55.     }
  56.     arcp = (arctype *) calloc( 1 , sizeof *arcp );
  57.     arcp -> arc_parentp = parentp;
  58.     arcp -> arc_childp = childp;
  59.     arcp -> arc_count = count;
  60.     /*
  61.      *    prepend this child to the children of this parent
  62.      */
  63.     arcp -> arc_childlist = parentp -> children;
  64.     parentp -> children = arcp;
  65.     /*
  66.      *    prepend this parent to the parents of this child
  67.      */
  68.     arcp -> arc_parentlist = childp -> parents;
  69.     childp -> parents = arcp;
  70. }
  71.  
  72.     /*
  73.      *    the code below topologically sorts the graph (collapsing cycles),
  74.      *    and propagates time bottom up and flags top down.
  75.      */
  76.  
  77.     /*
  78.      *    the topologically sorted name list pointers
  79.      */
  80. nltype    **topsortnlp;
  81.  
  82. topcmp( npp1 , npp2 )
  83.     nltype    **npp1;
  84.     nltype    **npp2;
  85. {
  86.     return (*npp1) -> toporder - (*npp2) -> toporder;
  87. }
  88.  
  89. nltype **
  90. doarcs()
  91. {
  92.     nltype    *parentp, **timesortnlp;
  93.     arctype    *arcp;
  94.     long    index;
  95.  
  96.     /*
  97.      *    initialize various things:
  98.      *        zero out child times.
  99.      *        count self-recursive calls.
  100.      *        indicate that nothing is on cycles.
  101.      */
  102.     for ( parentp = nl ; parentp < npe ; parentp++ ) {
  103.     parentp -> childtime = 0.0;
  104.     arcp = arclookup( parentp , parentp );
  105.     if ( arcp != 0 ) {
  106.         parentp -> ncall -= arcp -> arc_count;
  107.         parentp -> selfcalls = arcp -> arc_count;
  108.     } else {
  109.         parentp -> selfcalls = 0;
  110.     }
  111.     parentp -> propfraction = 0.0;
  112.     parentp -> propself = 0.0;
  113.     parentp -> propchild = 0.0;
  114.     parentp -> printflag = FALSE;
  115.     parentp -> toporder = DFN_NAN;
  116.     parentp -> cycleno = 0;
  117.     parentp -> cyclehead = parentp;
  118.     parentp -> cnext = 0;
  119.     if ( cflag ) {
  120.         findcall( parentp , parentp -> value , (parentp+1) -> value );
  121.     }
  122.     }
  123.     /*
  124.      *    topologically order things
  125.      *    if any node is unnumbered,
  126.      *        number it and any of its descendents.
  127.      */
  128.     for ( parentp = nl ; parentp < npe ; parentp++ ) {
  129.     if ( parentp -> toporder == DFN_NAN ) {
  130.         dfn( parentp );
  131.     }
  132.     }
  133.     /*
  134.      *    link together nodes on the same cycle
  135.      */
  136.     cyclelink();
  137.     /*
  138.      *    Sort the symbol table in reverse topological order
  139.      */
  140.     topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
  141.     if ( topsortnlp == (nltype **) 0 ) {
  142.     fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
  143.     }
  144.     for ( index = 0 ; index < nname ; index += 1 ) {
  145.     topsortnlp[ index ] = &nl[ index ];
  146.     }
  147.     qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
  148. #   ifdef DEBUG
  149.     if ( debug & DFNDEBUG ) {
  150.         printf( "[doarcs] topological sort listing\n" );
  151.         for ( index = 0 ; index < nname ; index += 1 ) {
  152.         printf( "[doarcs] " );
  153.         printf( "%d:" , topsortnlp[ index ] -> toporder );
  154.         printname( topsortnlp[ index ] );
  155.         printf( "\n" );
  156.         }
  157.     }
  158. #   endif DEBUG
  159.     /*
  160.      *    starting from the topological top,
  161.      *    propagate print flags to children.
  162.      *    also, calculate propagation fractions.
  163.      *    this happens before time propagation
  164.      *    since time propagation uses the fractions.
  165.      */
  166.     doflags();
  167.     /*
  168.      *    starting from the topological bottom, 
  169.      *    propogate children times up to parents.
  170.      */
  171.     dotime();
  172.     /*
  173.      *    Now, sort by propself + propchild.
  174.      *    sorting both the regular function names
  175.      *    and cycle headers.
  176.      */
  177.     timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
  178.     if ( timesortnlp == (nltype **) 0 ) {
  179.     fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami );
  180.     }
  181.     for ( index = 0 ; index < nname ; index++ ) {
  182.     timesortnlp[index] = &nl[index];
  183.     }
  184.     for ( index = 1 ; index <= ncycle ; index++ ) {
  185.     timesortnlp[nname+index-1] = &cyclenl[index];
  186.     }
  187.     qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
  188.     for ( index = 0 ; index < nname + ncycle ; index++ ) {
  189.     timesortnlp[ index ] -> index = index + 1;
  190.     }
  191.     return( timesortnlp );
  192. }
  193.  
  194. dotime()
  195. {
  196.     int    index;
  197.  
  198.     cycletime();
  199.     for ( index = 0 ; index < nname ; index += 1 ) {
  200.     timepropagate( topsortnlp[ index ] );
  201.     }
  202. }
  203.  
  204. timepropagate( parentp )
  205.     nltype    *parentp;
  206. {
  207.     arctype    *arcp;
  208.     nltype    *childp;
  209.     double    share;
  210.     double    propshare;
  211.  
  212.     if ( parentp -> propfraction == 0.0 ) {
  213.     return;
  214.     }
  215.     /*
  216.      *    gather time from children of this parent.
  217.      */
  218.     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
  219.     childp = arcp -> arc_childp;
  220.     if ( arcp -> arc_count == 0 ) {
  221.         continue;
  222.     }
  223.     if ( childp == parentp ) {
  224.         continue;
  225.     }
  226.     if ( childp -> propfraction == 0.0 ) {
  227.         continue;
  228.     }
  229.     if ( childp -> cyclehead != childp ) {
  230.         if ( parentp -> cycleno == childp -> cycleno ) {
  231.         continue;
  232.         }
  233.         if ( parentp -> toporder <= childp -> toporder ) {
  234.         fprintf( stderr , "[propagate] toporder botches\n" );
  235.         }
  236.         childp = childp -> cyclehead;
  237.     } else {
  238.         if ( parentp -> toporder <= childp -> toporder ) {
  239.         fprintf( stderr , "[propagate] toporder botches\n" );
  240.         continue;
  241.         }
  242.     }
  243.     if ( childp -> ncall == 0 ) {
  244.         continue;
  245.     }
  246.         /*
  247.          *    distribute time for this arc
  248.          */
  249.     arcp -> arc_time = childp -> time
  250.                     * ( ( (double) arcp -> arc_count ) /
  251.                     ( (double) childp -> ncall ) );
  252.     arcp -> arc_childtime = childp -> childtime
  253.                     * ( ( (double) arcp -> arc_count ) /
  254.                     ( (double) childp -> ncall ) );
  255.     share = arcp -> arc_time + arcp -> arc_childtime;
  256.     parentp -> childtime += share;
  257.         /*
  258.          *    ( 1 - propfraction ) gets lost along the way
  259.          */
  260.     propshare = parentp -> propfraction * share;
  261.         /*
  262.          *    fix things for printing
  263.          */
  264.     parentp -> propchild += propshare;
  265.     arcp -> arc_time *= parentp -> propfraction;
  266.     arcp -> arc_childtime *= parentp -> propfraction;
  267.         /*
  268.          *    add this share to the parent's cycle header, if any.
  269.          */
  270.     if ( parentp -> cyclehead != parentp ) {
  271.         parentp -> cyclehead -> childtime += share;
  272.         parentp -> cyclehead -> propchild += propshare;
  273.     }
  274. #    ifdef DEBUG
  275.         if ( debug & PROPDEBUG ) {
  276.         printf( "[dotime] child \t" );
  277.         printname( childp );
  278.         printf( " with %f %f %d/%d\n" ,
  279.             childp -> time , childp -> childtime ,
  280.             arcp -> arc_count , childp -> ncall );
  281.         printf( "[dotime] parent\t" );
  282.         printname( parentp );
  283.         printf( "\n[dotime] share %f\n" , share );
  284.         }
  285. #    endif DEBUG
  286.     }
  287. }
  288.  
  289. cyclelink()
  290. {
  291.     register nltype    *nlp;
  292.     register nltype    *cyclenlp;
  293.     int            cycle;
  294.     nltype        *memberp;
  295.     arctype        *arcp;
  296.  
  297.     /*
  298.      *    Count the number of cycles, and initialze the cycle lists
  299.      */
  300.     ncycle = 0;
  301.     for ( nlp = nl ; nlp < npe ; nlp++ ) {
  302.         /*
  303.          *    this is how you find unattached cycles
  304.          */
  305.     if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
  306.         ncycle += 1;
  307.     }
  308.     }
  309.     /*
  310.      *    cyclenl is indexed by cycle number:
  311.      *    i.e. it is origin 1, not origin 0.
  312.      */
  313.     cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
  314.     if ( cyclenl == 0 ) {
  315.     fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" ,
  316.         whoami , ( ncycle + 1 ) * sizeof( nltype ) );
  317.     done();
  318.     }
  319.     /*
  320.      *    now link cycles to true cycleheads,
  321.      *    number them, accumulate the data for the cycle
  322.      */
  323.     cycle = 0;
  324.     for ( nlp = nl ; nlp < npe ; nlp++ ) {
  325.     if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
  326.         continue;
  327.     }
  328.     cycle += 1;
  329.     cyclenlp = &cyclenl[cycle];
  330.         cyclenlp -> name = 0;        /* the name */
  331.         cyclenlp -> value = 0;        /* the pc entry point */
  332.         cyclenlp -> time = 0.0;        /* ticks in this routine */
  333.         cyclenlp -> childtime = 0.0;    /* cumulative ticks in children */
  334.     cyclenlp -> ncall = 0;        /* how many times called */
  335.     cyclenlp -> selfcalls = 0;    /* how many calls to self */
  336.     cyclenlp -> propfraction = 0.0;    /* what % of time propagates */
  337.     cyclenlp -> propself = 0.0;    /* how much self time propagates */
  338.     cyclenlp -> propchild = 0.0;    /* how much child time propagates */
  339.     cyclenlp -> printflag = TRUE;    /* should this be printed? */
  340.     cyclenlp -> index = 0;        /* index in the graph list */
  341.     cyclenlp -> toporder = DFN_NAN;    /* graph call chain top-sort order */
  342.     cyclenlp -> cycleno = cycle;    /* internal number of cycle on */
  343.     cyclenlp -> cyclehead = cyclenlp;    /* pointer to head of cycle */
  344.     cyclenlp -> cnext = nlp;    /* pointer to next member of cycle */
  345.     cyclenlp -> parents = 0;    /* list of caller arcs */
  346.     cyclenlp -> children = 0;    /* list of callee arcs */
  347. #    ifdef DEBUG
  348.         if ( debug & CYCLEDEBUG ) {
  349.         printf( "[cyclelink] " );
  350.         printname( nlp );
  351.         printf( " is the head of cycle %d\n" , cycle );
  352.         }
  353. #    endif DEBUG
  354.         /*
  355.          *    link members to cycle header
  356.          */
  357.     for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { 
  358.         memberp -> cycleno = cycle;
  359.         memberp -> cyclehead = cyclenlp;
  360.     }
  361.         /*
  362.          *    count calls from outside the cycle
  363.          *    and those among cycle members
  364.          */
  365.     for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
  366.         for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
  367.         if ( arcp -> arc_parentp == memberp ) {
  368.             continue;
  369.         }
  370.         if ( arcp -> arc_parentp -> cycleno == cycle ) {
  371.             cyclenlp -> selfcalls += arcp -> arc_count;
  372.         } else {
  373.             cyclenlp -> ncall += arcp -> arc_count;
  374.         }
  375.         }
  376.     }
  377.     }
  378. }
  379.  
  380. cycletime()
  381. {
  382.     int            cycle;
  383.     nltype        *cyclenlp;
  384.     nltype        *childp;
  385.  
  386.     for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
  387.     cyclenlp = &cyclenl[ cycle ];
  388.     for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
  389.         if ( childp -> propfraction == 0.0 ) {
  390.             /*
  391.              * all members have the same propfraction except those
  392.              *    that were excluded with -E
  393.              */
  394.         continue;
  395.         }
  396.         cyclenlp -> time += childp -> time;
  397.     }
  398.     cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
  399.     }
  400. }
  401.  
  402.     /*
  403.      *    in one top to bottom pass over the topologically sorted namelist
  404.      *    propagate:
  405.      *        printflag as the union of parents' printflags
  406.      *        propfraction as the sum of fractional parents' propfractions
  407.      *    and while we're here, sum time for functions.
  408.      */
  409. doflags()
  410. {
  411.     int        index;
  412.     nltype    *childp;
  413.     nltype    *oldhead;
  414.  
  415.     oldhead = 0;
  416.     for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
  417.     childp = topsortnlp[ index ];
  418.         /*
  419.          *    if we haven't done this function or cycle,
  420.          *    inherit things from parent.
  421.          *    this way, we are linear in the number of arcs
  422.          *    since we do all members of a cycle (and the cycle itself)
  423.          *    as we hit the first member of the cycle.
  424.          */
  425.     if ( childp -> cyclehead != oldhead ) {
  426.         oldhead = childp -> cyclehead;
  427.         inheritflags( childp );
  428.     }
  429. #    ifdef DEBUG
  430.         if ( debug & PROPDEBUG ) {
  431.         printf( "[doflags] " );
  432.         printname( childp );
  433.         printf( " inherits printflag %d and propfraction %f\n" ,
  434.             childp -> printflag , childp -> propfraction );
  435.         }
  436. #    endif DEBUG
  437.     if ( ! childp -> printflag ) {
  438.         /*
  439.          *    printflag is off
  440.          *    it gets turned on by
  441.          *    being on -f list,
  442.          *    or there not being any -f list and not being on -e list.
  443.          */
  444.         if (   onlist( flist , childp -> name )
  445.         || ( !fflag && !onlist( elist , childp -> name ) ) ) {
  446.         childp -> printflag = TRUE;
  447.         }
  448.     } else {
  449.         /*
  450.          *    this function has printing parents:
  451.          *    maybe someone wants to shut it up
  452.          *    by putting it on -e list.  (but favor -f over -e)
  453.          */
  454.         if (  ( !onlist( flist , childp -> name ) )
  455.         && onlist( elist , childp -> name ) ) {
  456.         childp -> printflag = FALSE;
  457.         }
  458.     }
  459.     if ( childp -> propfraction == 0.0 ) {
  460.         /*
  461.          *    no parents to pass time to.
  462.          *    collect time from children if
  463.          *    its on -F list,
  464.          *    or there isn't any -F list and its not on -E list.
  465.          */
  466.         if ( onlist( Flist , childp -> name )
  467.         || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
  468.             childp -> propfraction = 1.0;
  469.         }
  470.     } else {
  471.         /*
  472.          *    it has parents to pass time to, 
  473.          *    but maybe someone wants to shut it up
  474.          *    by puttting it on -E list.  (but favor -F over -E)
  475.          */
  476.         if (  !onlist( Flist , childp -> name )
  477.         && onlist( Elist , childp -> name ) ) {
  478.         childp -> propfraction = 0.0;
  479.         }
  480.     }
  481.     childp -> propself = childp -> time * childp -> propfraction;
  482.     printtime += childp -> propself;
  483. #    ifdef DEBUG
  484.         if ( debug & PROPDEBUG ) {
  485.         printf( "[doflags] " );
  486.         printname( childp );
  487.         printf( " ends up with printflag %d and propfraction %f\n" ,
  488.             childp -> printflag , childp -> propfraction );
  489.         printf( "time %f propself %f printtime %f\n" ,
  490.             childp -> time , childp -> propself , printtime );
  491.         }
  492. #    endif DEBUG
  493.     }
  494. }
  495.  
  496.     /*
  497.      *    check if any parent of this child
  498.      *    (or outside parents of this cycle)
  499.      *    have their print flags on and set the 
  500.      *    print flag of the child (cycle) appropriately.
  501.      *    similarly, deal with propagation fractions from parents.
  502.      */
  503. inheritflags( childp )
  504.     nltype    *childp;
  505. {
  506.     nltype    *headp;
  507.     arctype    *arcp;
  508.     nltype    *parentp;
  509.     nltype    *memp;
  510.  
  511.     headp = childp -> cyclehead;
  512.     if ( childp == headp ) {
  513.         /*
  514.          *    just a regular child, check its parents
  515.          */
  516.     childp -> printflag = FALSE;
  517.     childp -> propfraction = 0.0;
  518.     for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
  519.         parentp = arcp -> arc_parentp;
  520.         if ( childp == parentp ) {
  521.         continue;
  522.         }
  523.         childp -> printflag |= parentp -> printflag;
  524.         /*
  525.          *    if the child was never actually called
  526.          *    (e.g. this arc is static (and all others are, too))
  527.          *    no time propagates along this arc.
  528.          */
  529.         if ( childp -> ncall ) {
  530.         childp -> propfraction += parentp -> propfraction
  531.                         * ( ( (double) arcp -> arc_count )
  532.                           / ( (double) childp -> ncall ) );
  533.         }
  534.     }
  535.     } else {
  536.         /*
  537.          *    its a member of a cycle, look at all parents from 
  538.          *    outside the cycle
  539.          */
  540.     headp -> printflag = FALSE;
  541.     headp -> propfraction = 0.0;
  542.     for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
  543.         for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
  544.         if ( arcp -> arc_parentp -> cyclehead == headp ) {
  545.             continue;
  546.         }
  547.         parentp = arcp -> arc_parentp;
  548.         headp -> printflag |= parentp -> printflag;
  549.             /*
  550.              *    if the cycle was never actually called
  551.              *    (e.g. this arc is static (and all others are, too))
  552.              *    no time propagates along this arc.
  553.              */
  554.         if ( headp -> ncall ) {
  555.             headp -> propfraction += parentp -> propfraction
  556.                         * ( ( (double) arcp -> arc_count )
  557.                           / ( (double) headp -> ncall ) );
  558.         }
  559.         }
  560.     }
  561.     for ( memp = headp ; memp ; memp = memp -> cnext ) {
  562.         memp -> printflag = headp -> printflag;
  563.         memp -> propfraction = headp -> propfraction;
  564.     }
  565.     }
  566. }
  567.